package sort

func quickSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}
	var (
		left  []int = make([]int, 0)
		right []int = make([]int, 0)
	)
	for i := range arr {
		if arr[i] < arr[0] {
			left = append(left, arr[i])
		} else if arr[i] > arr[0] {
			right = append(right, arr[i])
		}
	}
	left = quickSort(left)
	right = quickSort(right)
	return append(append(left, arr[0]), right...)
}
